/*
*线性表的链式存储及功能
*@author 寇戈
*@version 1.0 , 2021-9-28
*/
#include <iostream>
#include "myhead.h"
#include <malloc.h>

using namespace std;

typedef struct LNode
{
    //线性表的单链表存储结构
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

int ListLength_L(LinkList L)
{
    /*
	* 获取链表长度
	* T(n)=O(n)
	*/
    LNode *p = L->next;
    int j = 0;
    while (p)
    {
        p = p->next;
        j++;
    }
    return j;
}

Status GetElem_L(LinkList L, int i, ElemType &e)
{
    /*
	* 读取元素操作
	* T(n)=O(n)
	*/

    LNode *p = L->next;
    int j = 1;
    while (p && j < i)
    {
        p = p->next;
        j++;
    }
    if (!p || j > i)
        return ERROR;
    e = p->data;
    return OK;
}

int LocateElem_L(LinkList L, ElemType e)
{
    /*
	* 读取元素操作
	* T(n)=O(n)
	*/
    LNode *p = L;
    int j = 0;
    while (p && p->data != e)
    {
        p = p->next;
        j++;
    }
    if (p->data == e)
        return j;
    return 0;
}

Status CreatList_L(LinkList &L, int n, char method)
{
    /*
	* 建立带表头结点的单链线性表
    *param:
    *    method:'b':before,前插法
    *           'a':after,后插法
	* T(n)=O(n)
	*/

    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    switch (method)
    {
    case 'b':
        //前插法
        L = (LinkList)malloc(sizeof(LNode));
        L->next = NULL;
        for (int i = n; i > 0; i--)
        {
            LNode *p = (LinkList)malloc(sizeof(LNode));
            cin >> p->data;
            p->next = L->next;
            L->next = p;
        }
        break;
    case 'a':
        //后插法
        LinkList r = L;
        for (int i = 1; i <= n; i++)
        {
            LinkList p = (LinkList)malloc(sizeof(LNode));
            cin >> p->data;
            //p->data = 2 * i - 1;
            r->next = p;
            r = p;
            r->next = NULL;
        }
        break;
    }

    return OK;
}

Status ListInsert_L(LinkList &L, int i, ElemType e)
{
    /*
	* 在带头结点的单链线性表中第i个位置之前插入元素
	* T(n)=O(n)
	*/

    LNode *p = L;
    int j = 0;

    //寻找i-1个节点
    while (p && j < i - 1)
    {
        p = p->next;
        j++;
    }
    //判断添加位置是否合理
    if (!p || j > i - 1)
        return ERROR;

    //新建节点
    LinkList s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

Status ListDelete_L(LinkList &L, int i, ElemType &e)
{
    /*
	* 删除元素
	* T(n)=O(n)
	*/

    LNode *p = L;
    int j = 0;

    while (p && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1)
        return ERROR;

    LinkList q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return OK;
}

Status showList(LinkList &L)
{
    /*
	* 遍历元素操作
	* T(n)=O(n)
	*/
    LinkList q = L->next;
    while (q)
    {
        cout << q->data << " ";
        q = q->next;
    }
    cout << endl;
    return OK;
}
